# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        head, head.next = ListNode(-float("inf")), head
        now_note, end_note = head.next, head.next
        while now_note:
            if now_note.val < end_note.val:
                mid_note = head
                while now_note.val > mid_note.next.val:
                    mid_note = mid_note.next
                mid_note.next, now_note.next, now_note = now_note, mid_note.next, now_note.next
            else:
                end_note.next, now_note, end_note = now_note, now_note.next, now_note
        end_note.next = None
        return head.next
